#pragma once
#include<iostream>
using namespace std;

namespace Key {
	template<class K>
	struct BSTNode
	{
		K _key;
		BSTNode<K>* _left;
		BSTNode<K>* _right;
		BSTNode(const K& key)
			:_key(key),
			_left(nullptr),
			_right(nullptr)
		{
		}
	};
	template<class K>
	class BSTree {
		typedef BSTNode<K> Node;
	public:
		BSTree() = default;
		~BSTree()
		{
			Destory(_root);
			_root = nullptr;
		}
		bool InSert(const K& key)
		{
			if (_root == nullptr)
			{
				_root = new Node(key);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			else {
				parent->_left = cur;
			}
			return true;
		}
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key) {
					cur = cur->_left;
				}
				else if (cur->_key < key) {
					cur = cur->_right;
				}
				else {
					return true;
				}
			}
			return false;
		}
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else {
					if (cur->_left == nullptr)
					{
						if (parent == nullptr) {
							_root = cur->_right;
						}
						else {
							if (parent->_left == cur) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
						}
						return true;
					}
					else if (cur->_right == nullptr) {
						if (parent == nullptr) {
							_root = cur->_left;
						}
						else {
							if (parent->_left == cur) {
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
						}
						return true;
					}
					else {
						//找到右子树的最小（最左）节点
						Node* RightMin = cur->_right;
						Node* RightMinParent = cur;
						while (RightMin->_left)
						{
							RightMinParent = RightMin;
							RightMin = RightMin->_left;
						}
						//替换为右子树最左节点的值
						cur->_key = RightMin->_key;
						//如果最左节点的有右子树，将它合并到父节点
						if (RightMinParent->_left == RightMin) {
							RightMinParent->_left = RightMin->_right;
						}
						else {
							RightMinParent->_right = RightMin->_right;
						}
						//删除节点
						delete RightMin;
						return true;
					}
				}
			}
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) {
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
		void Destory(Node* root)
		{
			if (root == nullptr) {
				return;
			}
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr) {
				return nullptr;
			}
			Node* newRoot = new Node(root->_key);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}
		Node* _root = nullptr;
	};
}

namespace _Key_Value
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;
		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right;
		BSTNode(const K& key,const V& value)
			:_key(key),
			_value(value),
			_left(nullptr),
			_right(nullptr)
		{
		}
	};
	template<class K,class V>
	class BSTree {
		typedef BSTNode<K,V> Node;
	public:
		BSTree() = default;
		~BSTree()
		{
			Destory(_root);
			_root = nullptr;
		}
		bool InSert(const K& key,const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur != nullptr)
			{
				if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}
			cur = new Node(key,value);
			if (parent->_key < key) {
				parent->_right = cur;
			}
			else {
				parent->_left = cur;
			}
			return true;
		}
		BSTNode<K,V>* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key) {
					cur = cur->_left;
				}
				else if (cur->_key < key) {
					cur = cur->_right;
				}
				else {
					return cur;
				}
			}
			return nullptr;
		}
		bool Erase(const K& key)
		{
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else {
					if (cur->_left == nullptr)
					{
						if (parent == nullptr) {
							_root = cur->_right;
						}
						else {
							if (parent->_left == cur) {
								parent->_left = cur->_right;
							}
							else {
								parent->_right = cur->_right;
							}
						}
						return true;
					}
					else if (cur->_right == nullptr) {
						if (parent == nullptr) {
							_root = cur->_left;
						}
						else {
							if (parent->_left == cur) {
								parent->_left = cur->_left;
							}
							else {
								parent->_right = cur->_left;
							}
						}
						return true;
					}
					else {
						//找到右子树的最小（最左）节点
						Node* RightMin = cur->_right;
						Node* RightMinParent = cur;
						while (RightMin->_left)
						{
							RightMinParent = RightMin;
							RightMin = RightMin->_left;
						}
						//替换为右子树最左节点的值
						cur->_key = RightMin->_key;
						//如果最左节点的有右子树，将它合并到父节点
						if (RightMinParent->_left == RightMin) {
							RightMinParent->_left = RightMin->_right;
						}
						else {
							RightMinParent->_right = RightMin->_right;
						}
						//删除节点
						delete RightMin;
						return true;
					}
				}
			}
			return false;
		}
		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}
	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr) {
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " " << root->_value << endl;
			_InOrder(root->_right);
		}
		void Destory(Node* root)
		{
			if (root == nullptr) {
				return;
			}
			Destory(root->_left);
			Destory(root->_right);
			delete root;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr) {
				return nullptr;
			}
			Node* newRoot = new Node(root->_key,root->_value);
			newRoot->_left = Copy(root->_left);
			newRoot->_right = Copy(root->_right);
			return newRoot;
		}
		Node* _root = nullptr;
	};
}